'lintcode 两数和的最接近值'

Posted on | In

描述

给定整数数组num，从中找到两个数字使得他们和最接近target，返回两数和与 target 的差的 绝对值。

样例

样例1

输入: nums = [-1, 2, 1, -4] 并且 target = 4
输出: 1
解释:
最小的差距是1，(4 - (2 + 1) = 1).
样例2

输入: nums = [-1, -1, -1, -4] 并且 target = 4
输出: 6
解释:
最小的差距是6，(4 - (- 1 - 1) = 6).

挑战

Do it in O(nlogn) time complexity.

思考

先排序，使用首尾两个指针来遍历数组。返回最小值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    /**
     * @param nums: an integer array
     * @param target: An integer
     * @return: the difference between the sum and the target
     */
    int twoSumClosest(vector<int> &nums, int target) {
        // write your code here
        sort(nums.begin(), nums.end());
        int i = 0, j = nums.size()-1, dis = INT_MAX;
        while (i != j) {
            int temp = nums[i] + nums[j];
            dis = min(dis, abs(temp-target));
            if (dis == 0) return 0;
            if (temp > target) j--;
            else if(temp < target) i++;
        }
        return dis;
    }
};
-------------end of filethanks for reading-------------